Technical Field
The present invention relates generally to information processing and, in particular, to conjugate gradient solvers for linear systems.
Description of the Related Art
This invention relates generally to conjugate gradient solvers for linear systems of equations, and provides conjugate gradient solver apparatus for generating data defining a solution vector for such a linear system.
The solution of linear systems of equations is fundamental to numerous scientific and engineering applications. Efficient solution of large scale linear systems is critical for achieving high energy efficiency and fast turn-around times, as well as permitting handling of increasingly-complex problems in the real-world application in question.
Linear systems can be represented in general by Ax=b, where A is a (typically symmetric, positive-definite) matrix of dimensions n×n (i.e., n rows and n columns), and b is a vector of dimensions n×1 (n rows and 1 column). Linear system solvers provide processing apparatus for processing input data defining the elements of matrix A and vector b to generate data defining the solution vector x for the system. The processing operation can be performed in accordance with various known techniques for solving linear systems. These techniques can generally be divided into direct methods, which aim to provide a solution in a fixed number of steps, and iterative methods. Iterative methods aim to improve on a current solution in each successive iteration until a desired precision is achieved. The conjugate gradient method is a well-known technique which can be implemented as an iterative method for solving linear systems.
Through use of solver circuitry specifically adapted to the computational task in question, hardware linear system solvers can exploit the parallelism inherent in the solution process to offer efficient solver implementations. Use of a fixed-point data format for processing data items in the solver circuitry offers further efficiency advantages. Fixed-point solvers can be implemented with high computational density, low power, small circuit area and small data widths (e.g., 8 or 16 bits) for data items, enabling particularly fast and efficient operation. However, the small dynamic range offered by the fixed-point data format severely limits its application in linear system solvers. In general, fixed-point solvers can only be used in scenarios requiring very low precision or with a limited class of solution methods having constraints suited to a restricted dynamic range. One example involves the use of fixed-point solvers for implementing the Lanczos method after preconditioning of the input matrix A.
For linear system solvers based on the conjugate gradient method, use of a fixed-point data format would likely cause overflow errors and strongly distort the result. The solver would tend to abort after only a few iterations, returning a very inaccurate solution. To avoid this problem, state of the art conjugate gradient solvers use a floating-point data representation. While the floating-point format offers wide dynamic range, arithmetic operations are costly in terms of time, power and circuit area, frustrating the key objective of enhancing system efficiency.